The present invention relates generally to coding and decoding and, in particular, to a method and apparatus for Reed-Solomon coding and decoding.
Reed-Solomon coding is known in the art. As was first described in xe2x80x9cPolynomial codes over certain finite fields,xe2x80x9d Reed I. S. and Solomon G., Journal of Society of Industrial Application Mathematics 8, 300-304 (1960), Reed-Solomon Codes can be utilized during the transmission of data to eliminate errors in the received data. The encoders rely on the mathematics of Galois fields, which are disclosed is U.S. Pat. No. 4,142,174 and 4,567,594, the disclosures of which are incorporated by reference herein. In summary, Reed-Solomon codes are defined with code symbols from a Galois Field of numbers represented as GF(Q), where Q=2b is a positive integer power of 2. A Galois Field has a finite number of elements. GF(Q) has Q elements, that can be represented by 0 and Qxe2x88x921 consecutive powers, (xcex10, xcex11, . . . , xcex1Qxe2x88x921) of a special element (xcex1).
Many different methods of using Reed-Solomon encoders and decoders are known in the art. One such method for using Reed-Solomon codes in error correction is to append a set of parity symbols to the transmitted data, where the word xe2x80x9csymbolxe2x80x9d is used to represent b bits that form an element of GF(Q) field. The parity symbols are used to detect and correct errors in the transmitted data. More particularly, an encoder treats the message bits as blocks of symbols that form a message polynomial on GF(Q) and derives the parity symbols by dividing the message polynomial (X) by a code generating polynomial (G). The parity symbols are identified as the coefficients of the remainder polynomial (C). The parity symbols are appended to the message symbols to form the coefficients of a codeword polynomial. The code generating polynomial is selected to impart desired properties to the codeword so that the codeword will belong to a particular class of error-correcting group codes. During transmission, the codeword is transmitted by appending the parity symbols to the message data as tail bits which are utilized by the receiver to correct errors in the received message polynomial (R).
FIG. 1 shows a prior-art Reed-Solomon encoder, implemented as a shift-register polynomial division circuitry. As shown, the shift register is initialized with zeros in the delay elements (D). During each iteration, the mth data symbol Xm is multiplied with the content of the right most delay element to form the symbol Ym. The content of each delay element is then updated by summing the content of the delay element to its left and the product of the symbol Ym and Gm., where Gm""s are the coefficients of the code generating polynomial, i.e., G(z)=G0+G1z+. . . +GKxe2x88x921zKxe2x88x921+ZK. (An exception is the left most delay element, which is updated with the product G0Ym.)
The parity symbols are generated by continuing to update the shift register until the end of the message block. Upon completing the iteration for the last symbol of the message block, the content of the shift register becomes the parity symbols, where the right most delay element contains the first parity symbol to be appended to the message data by the transmitter.
To date the division processing is typically carried out by dedicated hardware (e.g., multipliers 101, delay circuitry 102, and adders 103), however, with the advancement of xe2x80x9csoftxe2x80x9d modems, the processing has been increasingly accomplished via a microprocessor/software combination.
Although soft modems have the capability to perform Reed-Solomon encoding/decoding, a problem exists in that the prior art implementation requires a lot of processing power. In the encoder described in FIG. 1, for each message symbol, K multiplications and additions are required. Although Galois Field addition is logical XOR operation that is typically supported in microprocessor instruction set, Galois field multiplication is rarely supported and takes multiple instruction cycles to complete. For high speed modems (e.g., ADSL modems or cable modems), the Reed-Solomon encoder needs to process on the order of million of message symbols per second. The total processing power or MIPS required would be a significant percentage of if not exceeding the total processing power of a typical microprocessor. As result, the entire modem function may be difficult to accomplish via a microprocessor. Even if the microprocessor were able to accomplish modem functions, for host processing or software modems, processing power used by the modem would not be available for other applications. Therefore a need exists for a method and apparatus for encoding/decoding that can be implemented in soft modems, yet does not utilize the MIPS required by prior-art soft modems.